package qsort

//快速排序
/**
	规则：
		 1.append设立左边和右边游标和坐标0为基础值
		 2.左边游标向右移动不能大于左边游标值并且发现小于基础值时候停止
		 3.右边游标向左移动不能小于右边游标值并且发现大于基础值时候停止
		 4.左边先移动 右边后移动
		 5.判断左边是否小于右边 是互换两个游标的值 重复2操作 否 退出循环 （当否条件成立时 说明左游标和右游标碰头了 此时左游标小于且等于基础值 左游标的左边全小于基础值右边全大于基础值）
		 6.把左游标和基础值互换
		 7.基于基础值把左边和右边拆成两个序列重复1操作

**/

//Sort v or int array
func Sort(v []int) {
	qsort(v, 0, len(v)-1)
}

func qsort(v []int, left, right int) {
	if left > right {
		return
	}

	temp := v[left]

	i, j := left, right

	for i < j {

		for v[j] >= temp && j > i {
			j--
		}

		for v[i] <= temp && i < j {
			i++
		}

		if i < j {
			v[i], v[j] = v[j], v[i]
		}

	}

	v[left] = v[i]
	v[i] = temp

	qsort(v, left, i-1)
	qsort(v, i+1, right)

}
